package com.yum.Iterator.Map.YAbstractMap.HashMap;

import com.yum.Iterator.Map.YAbstractMap.YAbstractMap;
import com.yum.Iterator.Map.YMap;
import com.yum.Iterator.Set.YSet;
import com.yum.Iterator.Tree.YTree;

import java.io.Serializable;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.Arrays;
import java.util.HashMap;

public class YHashMap<K,V> extends YAbstractMap<K,V>
        implements YMap<K,V>,Cloneable, Serializable {

    private static final long serialVersionUID = 8259963189721233241L;

    /**
     * 负载因子默认大小
     */
    static final float DEAULT_LOAD_FACTOR = 0.75f;

    /**
     * 链表最大结点数，当结点数大于8时链表变成红黑树
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 红黑树最小结点数，当结点数小于6时红黑树变成单链表
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * 初始容量大小
     */
    static final int INITIAL_CAPACITY = 16;

    /**
     * 最大容量大小 1<<30 = 1,0000,0000,0000
     */
    static final int MAX_CAPACITY = 1 << 30;

    /**
     * 若元素数组长度小于这个值,则没有必要去进行结构转化
     * 若数组小于这个数,会先尝试扩容
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

    transient YNode<K,V>[] table;

    transient YSet<YEntry<K,V>> entryYSet;

    transient int size;

    transient int modCount;

    /**
     * size大于threshold会进行扩容
     * 下一次扩容的大小
     */
    int threshold;

    /**
     * 加载因子
     */
    final float loadFactor;

    /**
     * 以下三个方法具体实现在YLinkedHashMap
     */
    void afterNodeAccess(YNode<K,V> p){}
    void afterNodeInsertion(boolean evict){}
    void afterNodeRemoval(YNode<K,V> p){}

    public YHashMap(){
        loadFactor = DEAULT_LOAD_FACTOR;
    }

    public YHashMap(int initCapacity,float loadFactor){
        if(initCapacity < 0 || loadFactor <= 0)
            throw new IllegalArgumentException("长度错误");
        initCapacity = initCapacity > MAX_CAPACITY ? MAX_CAPACITY : initCapacity;
        this.loadFactor = loadFactor;
        this.threshold = tableSizeOf(initCapacity);
    }

    public YHashMap(int initCapacity){
        this(initCapacity,DEAULT_LOAD_FACTOR);
    }


    /**
     * 链表节点
     * @param <K>
     * @param <V>
     */
    static class YNode<K,V> implements YEntry<K,V>{

        final int hash;
        final K key;
        V value;
        YNode<K,V> next;

        public YNode(int hash, K key, V value, YNode<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }

        @Override
        public V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        @Override
        public String toString() {
            return key + "=" + value;
        }

        @Override
        public boolean equals(Object obj) {
            if(obj == this)
                return true;
            if(obj instanceof YEntry){
                YEntry<K,V> kvyEntry = (YEntry<K, V>) obj;
                return YAbstractMap.compare(kvyEntry.getKey(), key) &&
                        YAbstractMap.compare(kvyEntry.getValue(), value);
            }
            return false;
        }
    }

    /**
     * 树节点
     * 树节点 extends 链表节点 更加方便的去遍历和查看父或子节点
     * @param <K>
     * @param <V>
     */
    static final class YTreeNode<K,V> extends YLinkedHashMap.YEntry<K,V>{
        YTreeNode<K,V> parent;
        YTreeNode<K,V> leftChild;
        YTreeNode<K,V> rightChild;
        YTreeNode<K,V> prev;//前方结点
        boolean red;

        public YTreeNode(int hash, K key, V value, YNode<K, V> next) {
            super(hash, key, value, next);
        }

        /**
         *
         * @return 返回当前红黑树的根结点
         */
        final YTreeNode<K,V> root(){
            YTreeNode<K,V> r = this,p;
            for(;;){
                p = r.parent;
                if(p == null)
                    return r;
                r = p;
            }
        }

        /**
         * 左旋
         * @param root 根
         * @param p 父节点
         * @param <K> key
         * @param <V> value
         * @return 根
         */
        static <K,V> YTreeNode<K,V> leftRotate(YTreeNode<K,V> root,YTreeNode<K,V> p){
            //r:right pp:parent.parent rl:right.left
            YTreeNode<K,V> r,pp,rl;
            if(p != null && (r = p.rightChild) != null){
                if((rl = p.rightChild = r.leftChild) != null)
                    rl.parent = p;
                if((pp = r.parent = p.parent) == null)
                    (root = r).red = false;
                else if (pp.leftChild == p)
                    pp.leftChild = r;
                else
                    pp.rightChild = r;
                r.leftChild = p;
                p.parent = r;
            }
            return root;
        }

        /**
         * 右旋
         * @param root 根
         * @param p 父节点
         * @param <K> key
         * @param <V> value
         * @return 根
         */
        static <K,V> YTreeNode<K,V> rightRotate(YTreeNode<K,V> root,YTreeNode<K,V> p){
            //l: left pp:parent.parent lr:left.right
            YTreeNode<K,V> l,pp,lr;
            if(p!=null && (l = p.leftChild) != null){
                if((lr = p.leftChild = l.rightChild) != null)
                    lr.parent = p;
                if((pp = l.parent = p.parent) == null)
                    (root = l).red = false;
                else if(pp.rightChild == p)
                    pp.rightChild = l;
                else
                    pp.leftChild = l;
                l.rightChild = p;
                p.parent = l;
            }
            return root;
        }

        /**
         * put value
         * @param map this map
         * @param tab tab
         * @param h hash
         * @param k key
         * @param v value
         * @return Treenode
         */
        final YTreeNode<K,V> putTreeVal(YHashMap<K,V> map,YNode<K,V>[] tab,
                                        int h,K k,V v){
            Class<?> kc = null;
            boolean searched = false;   //标识是否被搜索过
            //定位root
            YTreeNode<K,V> root = (parent != null) ? root() : this;
            for(YTreeNode<K,V> p = root;;){
                int dir,ph;K pk;
                //经典的查找过程
                if((ph = p.hash) > h)
                    dir = -1;
                else if(ph < h)
                    dir = 1;
                else if((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                //hash冲突
                //判断 若hash相同 但是k的equal不同
                else if ((kc == null &&
                        (kc = comparableClassFor(k)) == null || (dir = compareComparables(kc,k,pk)) == 0)){
                    if(!searched){
                        YTreeNode<K,V> q,ch;
                        searched = true;
                        //递归搜索
                        if(((ch = p.leftChild) != null && (q = ch.find(h,k,kc)) != null)
                                || ((ch = p.rightChild) != null && (q = ch.find(h,k,kc)) != null))
                            return q;
                    }
                    //说明红黑树中没有与之equals相等的  那就必须进行插入操作
                    //打破平衡的方法的 分出大小 结果 只有-1 1
                    dir = tieBreakOrder(k,pk);
                }

                //插入操作
                //xp 当前节点
                YTreeNode<K,V> xp = p;
                //经典的查找
                if((p = (dir <= 0) ? p.leftChild : p.rightChild) == null){
                    YNode<K,V> xpn = xp.next;
                    //创建节点
                    YTreeNode<K,V> x = map.newYTreeNode(h,k,v,xpn);
                    //经典的查找++
                    if(dir <= 0)
                        xp.leftChild = x;
                    else
                        xp.rightChild = x;
                    //维护双向链表关系
                    xp.next = x;
                    x.parent = x.prev = xp;
                    if(xpn != null)
                        ((YTreeNode<K,V>)xpn).prev = x;
                    //将root移到table数组的i 位置的第一个节点
                    //插入操作过红黑树之后 重新调整平衡
                    moveRootToFront(tab,balanceInsertion(root,x));
                    return null;
                }
            }
        }

        /**
         * 将红黑树的root节点移动到tab相对应的索引中
         * 在树化的过程中，所有节点的prev，next值均未改变，简单的理解为对双向链表进行维护
         * 经过左旋或者右旋操作后，双向链表头节点可能发生了变化，需要把根节点放到链表头节点
         * @param table
         * @param root
         * @param <K>
         * @param <V>
         */
        static <K,V> void moveRootToFront(YNode<K,V>[] table,YTreeNode<K,V> root){
            int n = table.length;
            if(table != null && root != null && n > 0){
                //获取root对应的index
                int index = root.hash & (n-1);
                YTreeNode<K,V> first = (YTreeNode<K, V>) table[index];
                if(root != first){
                    YNode<K,V> rn;
                    table[index] = root;
                    YTreeNode<K,V> rp = root.prev;
                    //重置红黑树根节点的上下级关系
                    if((rn = root.next) != null)
                        ((YTreeNode<K,V>)rn).prev = rp;
                    if(rp != null)
                        rp.next = rn;
                    if(first != null)
                        first.prev = root;
                    root.next = first;
                    root.prev = null;
                }
            }
            //assert(断言) assert false的时候会抛出一个报错，进程强制关闭
            assert checkInvariants(root);
        }


        /**
         * 移除指定节点
         * @param map map
         * @param tab the tab
         * @param movable 是否移动其他节点
         */
        final void removeTreeNode(YHashMap<K,V> map,YNode<K,V>[] tab,boolean movable){
            int n;
            if(tab == null || (n = tab.length) == 0)
                return;
            int index = (n-1) & hash;
            YTreeNode<K,V> first = (YTreeNode<K, V>) tab[index],root = first,rl;
            //succ:删除节点的后一个节点 pred:删除节点的前一个节点
            YTreeNode<K,V> succ = (YTreeNode<K, V>) next,pred = prev;
            //如果pred节点不存在，则表示当前节点为根节点
            //删除后succ节点成为根节点，用fist节点标记，并放在数组上
            if(pred == null)
                tab[index] = first = succ;
            else
                pred.next = succ;
            if(succ != null)
                succ.prev = pred;
            if(first == null)
                return;
            if(root.parent != null)
                root = root.root();
            //以上做法是先整理当前节点上的链表关系，接下来整理红黑树关系
            //根据当root节点和它的左右节点的一些情况，判断红黑树节点的数量
            //如果啥都没有 给我变链表
            if(root == null || (movable && (root.rightChild == null
                    || (rl = root.leftChild) == null
                    || rl.leftChild == null))){
                tab[index] = first.untreeify(map);
                return;
            }
            //replacement p节点删除后代替他的节点
            YTreeNode<K,V> p = this,pl = leftChild,pr = rightChild,replacement;
            //若左子树和右子树都存在 则找他的后继节点
            if(pl != null && pr != null){
                YTreeNode<K,V> s = pr,sl;
                while ((sl = s.leftChild) != null)
                    s = sl;
                //将s节点和p节点的颜色交换
                boolean c = s.red;
                s.red = p.red;
                p.red = c;
                YTreeNode<K,V> sr = s.rightChild,pp = p.parent;
                if(s == pr){
                    p.parent = s;
                    s.rightChild = p;
                }else{
                    YTreeNode<K,V> sp = s.parent;
                    if((p.parent = sp) != null){
                        if(s == sp.leftChild)
                            sp.leftChild = p;
                        else
                            sp.rightChild = p;
                    }
                    if((s.rightChild = pr) != null)
                        pr.parent = s;
                }
                //因为s节点的性质，s节点没有左节点
                //当下p节点和s节点交换了位置，所以将p节点的左节点指空
                p.leftChild = null;
                if((p.rightChild = sr) != null)
                    sr.parent = p;
                if((s.leftChild = pl) != null)
                    pl.parent = s;
                if ((s.parent = pp) == null)
                    root = s;
                else if (p == pp.leftChild)
                    pp.leftChild = s;
                else
                    pp.rightChild = s;
                if (sr != null)
                    replacement = sr;
                else
                    replacement = p;
            }else if(pl != null)
                replacement = pl;
            else if(pr != null)
                replacement = pr;
            else
                replacement = p;
            //将以下判断跟上述判断分开看，仅以p节点的当前位置性质，对replacement节点进行操作
            //如果replacement不是p节点
            //将p节点的父节点pp变成replacement节点的父节点
            if(replacement != p){
                YTreeNode<K,V> pp = replacement.parent = p.parent;
                if(pp == null)
                    root = replacement;
                else if(p == pp.leftChild)
                    pp.leftChild = replacement;
                else
                    pp.rightChild = replacement;
                p.leftChild = p.rightChild = p.parent = null;
            }
            //若p为红色，删除后不影响root节点,若是黑色则需要找到平衡后的节点
            YTreeNode<K,V> r = p.red ? root : balanceInsertion(root,replacement);
            if(replacement == p){
                YTreeNode<K,V> pp = p.parent;
                p.parent = null;
                //如果pp节点存在
                //根据p节点的位置，将pp节点的对应位置指空
                if(pp != null){
                    if(p == pp.leftChild)
                        pp.leftChild = null;
                    else if(p == pp.rightChild)
                        pp.rightChild = null;
                }
            }
            //将新的根节点移动到数组上
            if(movable)
                moveRootToFront(tab,r);

        }

        /**
         * 验证红黑树的准确性
         * 确保红黑树的规则
         *
         * @param t 根节点
         * @param <K> key
         * @param <V> value
         * @return false为错误
         */
        static <K,V> boolean checkInvariants(YTreeNode<K,V> t){
            YTreeNode<K,V> tp = t.parent;
            YTreeNode<K,V> tl = t.leftChild;
            YTreeNode<K,V> tr = t.rightChild;
            YTreeNode<K,V> tb = t.prev;
            YTreeNode<K,V> tn = (YTreeNode<K, V>) t.next;
            if(tb != null && tb.next != t)//检查t与它的前驱节点是否绑定正确
                return false;
            if(tn != null && tn.prev != t)//检查t与它的后驱节点是否绑定正确
                return false;
            //检查父节点是否存在,若存在则检查t是否是父节点的左子节点或右子节点
            if(tp != null && t != tp.leftChild && t != tp.rightChild)
                return false;
            //若左子节点存在，检查左子节点的父节点是不是当前节点，检查左子节点hash值是否大于当前节点hash值
            if(tl != null && (tl.parent != t || tl.hash > t.hash))
                return false;
            //若右子节点存在，检查右子节点的父节点是不是当前节点，检查右子节点hash值是否小于当前节点hash值
            if(tr != null && (tr.parent != t || tr.hash < t.hash))
                return false;
            //检查当前节点是否为红色，和子节点是否为红色
            if(t.red && tl != null && tl.red && tr != null && tr.red)
                return false;
            //递归检查子节点
            if((tl != null && !checkInvariants(tl)) || (tr != null && !checkInvariants(tr)))
                return false;
            return true;
        }

        /**
         * 查找对应节点
         * 查找过程和查找二叉树的查找过程是一样的
         *
         * @param h hash
         * @param k key
         * @param kc keyClass
         * @return YTreeNode
         */
        final YTreeNode<K,V> find(int h,Object k,Class<?> kc){
            YTreeNode<K,V> p = this;
            do{
                int ph,dir;
                K pKey;
                YTreeNode<K,V> pl = p.leftChild,pr = p.rightChild,q;
                if((ph = p.hash) > h)
                    p = pl;
                else  if(ph < h)
                    p = pr;
                else if((pKey = p.key) == k || (k!=null&&k.equals(pKey)))
                    return p;
                else if(pl == null)
                    p = pr;
                else if(pr == null)
                    p = pl;
                //左右两边都不为空，则判断kc是否为Comparable的实现类
                //按key的值进行比较
                else if ((kc != null ||
                        (kc = comparableClassFor(k)) != null) &&
                        (dir = compareComparables(kc,k,pKey)) != 0)
                    p = dir < 0 ? pl : pr;
                //如果上述情况都不成立,则递归查找,先递归判断右子树，若查找不到,则继续递归判断左子树
                else if((q = pr.find(h,k,kc)) != null)
                    return q;
                else
                    p = pl;
            }while (p != null);
            return null;
        }

        /**
         * 遍历整个链表,将链表变成红黑树
         * @param tab
         */
        final void treeify(YNode<K,V>[] tab){
            YTreeNode<K,V> root = null;
            //定义树的根节点
            for(YTreeNode<K,V> o = this,next;o != null;o = next){
                //指向下一节点
                next = (YTreeNode<K,V>)o.next;
                //在使用之前将左右节点置空
                o.leftChild = o.rightChild = null;
                //判断root是否赋值,若没有则root指向o,并改为黑色节点,修改其parent为null
                if(root == null){
                    o.parent = null;
                    o.red = false;
                    root = o;
                }
                else {
                    //此时的root不为空,说明非第一次操作,将o节点添加到树中
                    K k = o.key;
                    int h = o.hash;
                    Class<?> kc =null;
                    for(YTreeNode<K,V> p = root;;){
                        int dir,ph;
                        K pk = p.key;
                        if((ph = p.hash) > h)
                            dir = -1;
                        else if(ph < h)
                            dir = 1;
                        else if ((kc == null && (kc = comparableClassFor(k)) == null) ||
                                (dir = compareComparables(kc,k,pk)) == 0)
                            dir = tieBreakOrder(k,pk);
                        //dir是比较完的结果,根据dir来判断插入左还是右
                        YTreeNode<K,V> op = p;
                        if((p = (dir < 0) ? p.leftChild : p.rightChild) == null){
                            o.parent = p;
                            if(dir < 0)
                                op.leftChild = o;
                            else
                                op.rightChild = o;
                            //插入后,再调用balanceInsertion确保红黑树的特性
                            root = balanceInsertion(root,o);
                            break;
                        }
                    }
                }
            }
        }

        /**
         * 当红黑树新插入一个节点时，需要对树重新优化，保证该树保持红黑树的特征
         * @param root 根
         * @param o 新插入的对象
         * @param <K> key
         * @param <V> value
         * @return 新插入的对象
         */
        static <K,V> YTreeNode<K,V> balanceInsertion(YTreeNode<K,V> root,YTreeNode<K,V> o){
            o.red = true;

            for (YTreeNode<K,V> op,opp,oppl,oppr;;){
                //判断o是否为根
                if((op = o.parent) == null){
                    o.red = false;
                    return o;
                }
                //当op的颜色为黑色,或者op的颜色为红色且它的parent为null
                //一般不会出现op的颜色为红色且它的parent为null,主要是为了opp的赋值
                else if (!o.red || (opp = op.parent) == null)
                    return root;
                //如果op是它父节点的左子节点
                if(op == (oppl = opp.leftChild)){
                    if((oppr = opp.rightChild) != null && oppr.red){
                        oppr.red = false;
                        op.red = false;
                        opp.red = true;
                        o = opp;
                    }
                    else {
                        //当o为父节点右子节点,则需要左旋
                        if(o == op.rightChild){
                            root = leftRotate(root,o = op);
                            opp = (op = o.parent) == null ? null : op.parent;
                        }
                        if(op != null){
                            op.red = false;
                            if(opp != null){
                                opp.red = true;
                                root = rightRotate(root,opp);
                            }
                        }
                    }
                }else{
                    if(oppl != null && oppl.red){
                        oppl.red = false;
                        op.red = false;
                        opp.red = true;
                        o = opp;
                    }else {
                        if(o == op.leftChild){
                            root = rightRotate(root,o = op);
                            opp = (op = o.parent) == null ? null : op.parent;
                        }
                        if(op != null){
                            op.red = false;
                            if(opp != null){
                                opp.red = false;
                                root = leftRotate(root,opp);
                            }
                        }
                    }
                }
            }
        }


        /**
         * 从根节点开始寻找节点
         * @param h
         * @param k
         * @return
         */
        final YTreeNode<K,V> getYTreeNode(int h,Object k){
            return (parent != null ? root() : this).find(h,k,null);
        }

        /**
         * 比较两个对象的大小
         * Object.hashCode()默认返回内存地址,但是可能被重写之后返回的则可能不是内存地址
         * System.identityHashCode()返回对象的内存地址
         * @param a 对象a
         * @param b 对象b
         * @return 比较结果
         */
        static int tieBreakOrder(Object a,Object b){
            int d;
            if(a == null || b == null ||
                    (d = a.getClass().getName().compareTo(b.getClass().getName())) == 0)
                //如果CompareTo方法不能解决,则通过System.identityHashCode方法比较
                d = (System.identityHashCode(a) <= System.identityHashCode(b)) ?
                        -1 : 1;
            return d;
        }

        /**
         * 将红黑树退化成链表
         * @param map map
         * @return node
         */
        final YNode<K,V> untreeify(YHashMap<K,V> map){
            //hd : 链表头 tl : 链表尾
            YNode<K,V> hd = null,tl = null;
            //遍历
            for(YNode<K,V> q = this;q != null;q = q.next){
                YNode<K,V> p = map.replacementNode(q,null);
                if(tl == null)
                    hd = p;
                else
                    tl.next = p;
            }
            return hd;
        }


        /**
         * 将红黑树的节点拆分为高位和低位红黑树,若树不达标准(太小),则取消树化
         *
         * @param map map
         * @param tab tab[]
         * @param index 红黑树索引
         * @param bit 数组容量
         */
        final void split(YHashMap<K,V> map,YNode<K,V>[] tab,int index,int bit){
            //当前节点 b
            YTreeNode<K,V> b = this;
            YTreeNode<K,V> loHead = null,loTail = null;
            YTreeNode<K,V> hiHead = null,hiTail = null;
            //高位与低位的节点数
            int lc = 0,hc = 0;
            for(YTreeNode<K,V> e = b,next;e != null;e = next){
                next = (YTreeNode<K,V>)e.next;
                e.next = null;
                if((e.hash & bit) == 0){
                    if((e.prev = loTail) == null)
                        loTail = e;
                    else
                        loTail.next = e;
                    loTail = e;
                    ++lc;
                }else{
                    if((e.prev = hiTail) == null)
                        hiTail = e;
                    else
                        hiTail.next = e;
                    hiTail = e;
                    ++hc;
                }
            }

            //判断是否需要退化成链表
            if(loHead != null){
                if(lc < UNTREEIFY_THRESHOLD)
                    tab[index] = loHead.untreeify(map);
                else{
                    tab[index] = loHead;
                    if(hiHead != null)
                        //如果高位红黑树存在，不存在则说明原先的节点都还在当前红黑树上。不用变化
                        //否则将低位红黑树重新树化，虽然已经当前还是红黑树
                        //但是节点改变了，所以要重新再来一遍，梳理节点
                        loHead.treeify(tab);
                }
            }
            if(hiHead != null){
                if(hc < UNTREEIFY_THRESHOLD)
                    tab[index] = hiHead.untreeify(map);
                else{
                    tab[index + bit] = hiHead;
                    if(loHead != null)
                        hiHead.treeify(tab);
                }
            }
        }

    }

    /**
     * 当hash值相同时候会调用此方法
     * 如果对象的类实现了Comparable<C>接口，那么返回C
     * @param o 对象
     * @return 类
     */
    static Class<?> comparableClassFor(Object o){
        if(o instanceof Comparable){
            Class<?> c;
            Type[] ts,as;
            Type t;
            ParameterizedType p;
            //如果o是字符串对象则返回 String类实现了Comparable接口
            if((c = o.getClass()) == String.class)
                return c;
            if((ts = c.getGenericInterfaces()) != null){
                for (int i=0;i<ts.length;++i){
                    //如果当前接口t为泛型接口
                    //如果该泛型接口t的原始类型p是Comparable接口
                    //如果该Comparable接口p自定义了一个泛型参数
                    //如果这一个泛型参数的类型就是c，则返回
                    if((t = ts[i])instanceof ParameterizedType &&
                        (p=(ParameterizedType)t).getRawType() == Comparable.class &&
                        (as = p.getActualTypeArguments()) != null &&
                        as.length == 1 && as[0] == c)
                        return c;
                }
            }
        }
        return null;
    }

    /**
     * 如果o的类型是kc，返回k.compareTo(o)的比较结果
     * 如果o为空，或者类型不是kc，返回0;
     * @param kc keyClass
     * @param k key
     * @param o obj
     * @return 比较结果
     */
    static int compareComparables(Class<?> kc,Object k,Object o){
        return o == null || o.getClass() !=kc ? 0 : ((Comparable)k).compareTo(o);
    }

    /**
     * hashCode右移16位为32bit的一半。与自身做异或操作
     * 混合了哈希值的高位和低位,增加了低位的随机性。
     * 混合后也变相保持了高位的特征
     * 例:设x,y 前四位
     * x = 0011
     * y = 0101
     *
     * x&y = 0001 0和1的占比为 0.75:0.25
     * x|y = 0111 0和1的占比为 0.25:0.75
     * x^y = 0110 0和1的占比为 0.5:0.5
     * 可以发现使用异或运算(^)计算出来的hash更加平均，不容易出现冲突
     * @param key key
     * @return hashcode
     */
    static final int hashCode(Object key){
        int h;
        return key == null?0:(h=key.hashCode())^(h>>16);
    }

    /**
     *
     * @param cap 容量大小
     * @return threshold
     * 假设 cap = 100
     *  n = 99
     *  n = 0000 0000 0000 0000 0000 0000 0110 0011
     *  n |= n >>> 1 = 0000 0000 0000 0000 0000 0000 0111 0011 = 113
     *  n |= n >>> 2 = 0000 0000 0000 0000 0000 0000 0111 1111 = 127
     *  n |= n >>> 4 = 0000 0000 0000 0000 0000 0000 0111 1111 = 127
     *  n |= n >>> 8 = 0000 0000 0000 0000 0000 0000 0111 1111 = 127
     *  n |= n >>> 16 = 0000 0000 0000 0000 0000 0000 0111 1111 = 127
     *  最终return 为 128
     *  最后的容量总是或经常为偶数，这样可以减少哈希冲突。
     *  但总不是为偶数
     */
    static final int tableSizeOf(int cap){
        int n = cap - 1;
        n |= n >> 1;
        n |= n >> 2;
        n |= n >> 4;
        n |= n >> 8;
        n |= n >> 16;
        return (n < 0) ? 1 : (n>= MAX_CAPACITY) ? MAX_CAPACITY : n + 1;
    }

    /**
     * 新建链表节点
     */
    YNode<K,V> newNode(int hash,K key,V value,YNode<K,V> next){
        return new YNode<>(hash,key,value,next);
    }

    /**
     *  新建树节点
     */
    YTreeNode<K,V> newYTreeNode(int hash,K key,V value,YNode<K,V> next){
        return new YTreeNode<>(hash, key, value, next);
    }

    /**
     *
     * @param hash hash值
     * @param key key
     * @param value value
     * @param onlyIfAbsent 如果hash冲突时，是否替换新值 false为替换
     * @param evict 表是否在创建模式，false为创建模式
     * @return value
     */
    final V putValue(int hash,K key,V value,boolean onlyIfAbsent,boolean evict){
        YNode<K,V>[] tab;
        YNode<K,V> p;
        int n,i;
        //若tab 为空 则触发扩容机制
        if((tab=table)==null||(n=tab.length)==0)
            n = (tab = resize()).length;
        //若对应索引的根节点为空则新建
        if((p = tab[i = (n-1) & hash]) == null)
            tab[i] = newNode(hash,key,value,null);
        else {
            YNode<K,V> e;
            K k;
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //判断是否是树节点 是的话则调用putTreeVal()函数
            else if(p instanceof YTreeNode)
                e = ((YTreeNode<K,V>)p).putTreeVal(this,tab,hash,key,value);
            //hash寻址冲突 此时需要在链表上进行操作
            else {
                for(int binCount = 0;;++binCount){
                    if((e = p.next) == null){
                        p.next = newNode(hash,key,value,null);
                        //若超过树化阈值,则树化
                        if(binCount >= TREEIFY_THRESHOLD - 1)
                            treeifyBin(tab,hash);
                        break;
                    }
                    //此时在链表找尾节点时，发现了和新插入节点完全一致的key，所以记录，跳出，后文替换
                    if(e.hash == hash && ((k = key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //替换操作
            if(e != null){
                V oldVal = e.value;
                if(!onlyIfAbsent || oldVal == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldVal;
            }
        }
        ++modCount;
        if(++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

    /**
     * 扩容机制
     * @return
     */
    final YNode<K,V>[] resize(){
        YNode<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap,newThr = 0;
        //第一步:扩容
        //扩容 如果oldCap超过了整数的最大容量，就将threshold设置为整数最大值
        //如果没有超过则为原来的2倍
        if(oldCap > 0){
            if(oldCap >= MAX_CAPACITY){
                threshold = 0x7fffffff;
                return oldTab;
            }
            else if((newCap = oldCap << 1) < MAX_CAPACITY && oldCap > INITIAL_CAPACITY){
                newThr = oldThr << 1;
            }
        }
        //第二步:设置threshold
        //设置threshold
        //如果threshold已经初始化了就直接使用，否则初始化一个默认的容量和threshold
        else if (oldThr > 0)
            newCap = oldThr;
        else {
            newCap = INITIAL_CAPACITY;
            newThr = (int) (DEAULT_LOAD_FACTOR*INITIAL_CAPACITY);
        }
        //再次判断newThr
        if(newThr == 0){
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAX_CAPACITY && ft < (float) MAX_CAPACITY) ?
                    (int)ft:0x7fffffff;
        }
        //给threshold最终赋值
        threshold = newThr;

        //第三步:把旧数据复制到新数组
        YNode<K,V>[] newTable = new YNode[newCap];
        table = newTable;
        //判断原本的数组是否有数据
        if(oldTab != null){
            for(int j=0;j<oldCap;++j){
                YNode<K,V> node;
                if((node = oldTab[j]) != null){
                    oldTab[j] = null;
                    //判断node是否为链表 不是则重新计算index并存放
                    if(node.next == null)
                        newTable[node.hash & (newCap - 1)] = node;
                    else if(node instanceof YTreeNode)
                        ((YTreeNode<K,V>)node).split(this,newTable,j,oldCap);
                    else{
                        YNode<K,V> loHead = null,loTail = null;
                        YNode<K,V> hiHead = null,hiTail = null;
                        YNode<K,V> next;
                        do{
                            next = node.next;
                            if((node.hash & oldCap) == 0){
                                if(loTail == null)
                                    loHead = node;
                                else
                                    loTail.next = node;
                                loTail = node;
                            }else{
                                if(hiTail == null)
                                    hiHead = node;
                                else
                                    hiTail.next = node;
                                hiTail = node;
                            }
                        }while ((node = next) != null);
                        if(loTail != null){
                            loTail.next = null;
                            newTable[j] = loHead;
                        }
                        if(hiTail != null){
                            hiTail.next = null;
                            newTable[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTable;
    }

    /**
     * 链表树化
     * @param tab tab[]
     * @param hash hash
     */
    final void treeifyBin(YNode<K,V>[] tab,int hash){
        int n,index;YNode<K,V> e;
        if(tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        //如果长度大于MIN_TREEIFY_CAPACITY,那么就要进行结构转化了
        else if((e = tab[index = (n-1) & hash]) != null){
            //hd 头,tl 尾
            YTreeNode<K,V> hd = null,tl = null;
            do{
                //将链表节点转化成树节点
                YTreeNode<K,V> p = replacementTreeNode(e,null);
                //若tl为空证明无根节点
                if(tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                //当前节点设为尾节点
                tl = p;
            }while ((e = e.next) != null);

            //将转换后的双向链表树化
            if((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

    /**
     * 移除节点
     * @param hash hash for key
     * @param key the key
     * @param value the value
     * @param matchValue 若为true 则value equal 相等是移除
     * @param movable 若为false 则删除时不移动其它节点
     * @return the node
     */
    final YNode<K,V> removeNode(int hash,Object key,Object value,boolean matchValue,boolean movable){
        YNode<K,V>[] tab;
        YNode<K,V> p;
        int n,index;
        //查找节点
        if((tab = table) != null && (n = tab.length) > 0
                && (p = tab[index = (n-1) & hash]) != null){
            YNode<K,V> node = null,e;K k;V v;
            if(p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if((e = p.next) != null){
                //若是树节点则递归查找节点
                if(p instanceof YTreeNode)
                    node = ((YTreeNode<K,V>)p).getYTreeNode(hash,key);
                else {
                    do {
                        if(e.hash == hash
                                && ((k = e.key) == key
                                || (key != null && key.equals(k)))){
                            node = e;
                            break;
                        }
                    }while ((e = e.next) != null);
                }
            }
            if(node != null && (!matchValue || (v = node.value) == value
                    || (value != null && value.equals(v)))){
                if(node instanceof YTreeNode)
                    ((YTreeNode<K,V>)node).removeTreeNode(this,tab,movable);
                else if(node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

    /**
     * getNode
     * @param hash hash
     * @param key key
     * @return the node
     */
    final YNode<K,V> getNode(int hash,Object key){
        YNode<K,V>[] tab;YNode<K,V> first,e;
        int n;K k;
        if((tab = table) != null && (n = tab.length) > 0
                && (first = tab[(n-1) & hash]) != null){
            if(first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if((e = first.next) != null){
                if(first instanceof YTreeNode)
                    return ((YTreeNode<K,V>)first).getYTreeNode(hash,key);
                do{
                    if(e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                }while ((e = e.next) != null);
            }
        }
        return null;
    }

    /**
     * 将树节点退化成链表节点
     * @param p p
     * @param next next
     * @return node
     */
    YNode<K,V> replacementNode(YNode<K,V> p,YNode<K,V> next){
        return new YNode<>(p.hash,p.key,p.value,next);
    }

    /**
     * 将链表节点变成树节点
     */
    YTreeNode<K,V> replacementTreeNode(YNode<K,V> p,YNode<K,V> next){
        return new YTreeNode<>(p.hash,p.key,p.value,next);
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public V put(K key, V value) {
        return putValue(hashCode(key),key,value,false,true);
    }

    @Override
    public V get(K key) {
        YNode<K,V> e;
        return (e = getNode(hashCode(key),key)) == null ? null : e.value;
    }

    @Override
    public V remove(K key) {
        YNode<K,V> e;
        return (e = removeNode(hashCode(key),key,null,false,true)) == null ?
                null : e.value;
    }

    @Override
    public String toString() {
        return null;
    }

    @Override
    public YSet<YEntry<K, V>> entrySet() {
        return null;
    }



}
